#include <vector>
#include <string>
#include <iostream>

using namespace std;

int levenshteinDistance(string str1, string str2) {
  vector<vector<int>> steps(
    str1.length() + 1,
    vector<int>(str2.length() + 1, 0)
  );

  // 先按行遍历
  // 在每一行里，按列遍历
  for (int row = 0; row < str1.length() + 1; ++row) {
    for (int col = 0; col < str2.length() + 1; ++col) {
      // steps[row][col]
      steps[row][col] = col;
    }

    steps[row][0] = row;
  }

  // ...
  // 再重新遍历一次 steps
  // 行列相同：斜上对角线的值
  // 否则：左、斜上、上的最小值 + 1

  return steps[str1.length()][str2.length()];
}

int main(int argc, char const *argv[])
{
  /* code */
  return 0;
}


